Randomized linear regression

Let 𝚷\mathbf{\Pi} be a properly scaled JL matrix (random , sparse random etc.) with m=O(dĪĩ2)m=O(\frac{d}{\epsilon^2}) rows1. Then with probability 9/109/10, for any 𝐀∈ℝn×d\mathbf{A} \in \mathbb{R}^{n \times d} and 𝐛∈ℝn\mathbf{b} \in \mathbb{R}^n, âˆĨ𝐀𝐱Ėƒâˆ’đ›âˆĨ22≤(1+Īĩ)âˆĨ𝐀𝐱*−𝐛âˆĨ22\lVert \mathbf{A}\tilde{\mathbf{x}}-\mathbf{b}\rVert_2^2 \leq (1+\epsilon)\lVert \mathbf{A}\mathbf{x}^*-\mathbf{b}\rVert_2^2 where 𝐱Ėƒ=argmin𝐱âˆĨ𝚷𝐀𝐱−𝚷𝐛âˆĨ22\tilde{\mathbf{x}} = \arg\min_\mathbf{x}\lVert \mathbf{\Pi Ax}-\mathbf{\Pi b}\rVert_2^2.


  1. this can be improved to O(d/Īĩ)O(d/\epsilon) with tighter analysis↩ī¸Ž